perm filename S2.PUB[D,LES]3 blob
sn#403161 filedate 1978-12-12 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00022 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 .device xgp
C00005 00003 .every heading()
C00007 00004 .s Summary
C00010 00005 .s A Pascal Extension for Systems Programming
C00015 00006 .app New Personnel
C00019 00007 .app Text of December 1977 Proposal
C00023 00008 .s Work Plan
C00027 00009 .ss Crossbar Switch Design
C00032 00010 .s Coordination and Reporting
C00035 00011 .app SAIL Background in System Development
C00043 00012 .bib
C00046 00013 .next page app Budget
C00050 00014 .every heading(,,{page})count page onecol select 7 verbatim
C00054 00015 .next page
C00059 00016 .next page
C00063 00017 .next page
C00067 00018 .next page
C00070 00019 .next page
C00075 00020 .next page
C00079 00021 .next page
C00082 00022 .next page
C00085 ENDMK
C⊗;
.device xgp
.if xcribl then start "xgp"
.require "bask.pub[sub,sys]" source_file;
.font 5 "metlb"; font 6 "metmb";
.font 7 "gacl25";
. end "xgp";
.sides←1;
.require "twocol.pub[sub,sys]" source_file;
.macro sskip ⊂skip(if lines<15 then 200 else 2)⊃; << section skip control >>
.macro appskip ⊂skip 200⊃; << appendix skip >>
.if ¬xcribl then start "tty"
. page frame 52 high 72 wide;
. title area heading lines 1 to 3
. area text lines 4 to 52;
. end "tty";
.
.MACRO BC ⊂ BEGIN PREFACE 0; INDENT 1,4; CRBREAK nojust ⊃
.
.MACRO BS ⊂ BEGIN PREFACE 0; INDENT 1,4; nojust ⊃
.
.MACRO IB ⊂ turn on "%";
.AT """" ⊂ (IF THISFONT=1 THEN "%3" ELSE "%1"); ⊃
.AT "<" ⊂ "%2" ⊃; AT ">" ⊂ "%1" ⊃;
. ⊃
.MACRO BIB ⊂ CB(References);
. BEGIN INDENT 0,3; NOJUST; IB;
. AT "AIM-" ⊂ "Stanford AI Memo AαIαMα-" ⊃;
. COUNT exref TO 200
. AT "⊗" ⊂ IF LINES<3 THEN NEXT COLUMN; NEXT EXREF; ("["&EXREF&"] ") ⊃
. ⊃
.SECNAME←"";
.portion some; place text;
.every heading();
.onecol;
.begin "cover"
.center; select 6;
November 1978
Proposal to
%5University of California
Lawrence Livermore Laboratory%6
for design of
%5An Operating System for the S-1 Computer%6
.skip 2
John McCarthy, Professor of Computer Science
Forest Baskett, Associate Professor of Computer Science
Co-principal Investigators
.skip 10;
Abstract
.skip
.begin fill;
The Stanford Artificial Intelligence Laboratory proposes to continue
participation in the Lawrence Livermore Laboratory program for development
of the S-1 computer system.
This proposal covers a one-year period beginning 1 January 1979.
.end
.skip 10
%5Computer Science Department
Stanford University
.end "cover"
.every heading(,"S-1 Proposal",{page});
.count page;
.if xcribl then twocol;
.s Summary
The Stanford Artificial Intelligence Laboratory proposes to continue
development work on the S1 computer system, as planned in our proposal of
December 1977 (Appendix B).
This proposal covers calendar year 1979.
In the period April 1978 to the present, the following has been accomplished.
.begin indent 4,7; nojust
1. Preliminary design of operating system.
2. Support programs have been developed as follows:
.begin preface 0; indent 7,10;crbreak
a. S1 simulator,
b. Cross-assembler for S1 code running on PDP-10,
c. S1 debugger,
d. PDP-10 simulator for S1,
e. AN UYK-7 simulator,
f. Memory diagnostic
.end
3. A set of numerical rountines has been written for the S1
(SQRT, SIN, COS, ATAN, LOG, EXP).
4. Detailed design and layout of the memory switch is well underway.
At this writing,
all data paths and about 90α% of the control logic have been designed.
Diagnostic hardware design is just beginning and physical layout
is yet to be done.
5. Assistance has been provided in other hardware design, mainly the
memory interface for the Mark I processor.
.end
Professor Forest Baskett has joined the project as Co-principal Investigator
and will coordinate system programming efforts. Professor John Hennessy
has also joined in this effort. See Appendix A for more on their interests.
.s A Pascal Extension for Systems Programming
An upward compatible extension of the Pascal programming language, designed
to support the development of large system programs, is described in the
attached note by John Hennessy and Forest Baskett, "An Extension to the
Programming Language Pascal to support Systems Programming".
.app New Personnel
.cb Forest Baskett
Forest Baskett has been involved in operating system design and
development since 1962. He worked with the Rice Computer and developed
parts of the Codeword based operating system for that computer in the
early '60s.
He was one of the principal designers and implementers of one
of the earliest and best time-sharing systems on CDC 6600's, the UT
operating system at the University of Texas. He was the principal
designer of DEMOS, a modern kernel based, process structured operating
system for the CRAY-1. He has published numerous papers on computing
system design and development.
.cb John Hennessy
Professor John Hennessy's research interests include programming language
design and implementation, operating systems design, and distributed systems.
In the area of programming language design he has designed a real-time
programming language, providing support for stand-alone systems. Recently,
under S-1 funding, he has worked on the design of an extension of the
programming language Pascal, to support systems programming on the S-1.
He has also been involved in the design and maintenance of two Pascal compilers.
Currently, he is initiating work on the problems of software portability
and interactive high level language debuggers.
Professor Hennessy is also conducting research on the topic of
distributed computing and its incorporation into a programming
language. This research is based on the incorporation of message
passing and synchronization capabilities into a standard process structure.
The goal is to provide simple tools to support the construction of reliable
distributed software systems. This is important to the S-1 project, since it
is reasonable to consider a message passing system within the operating
system, as well as available to the users.
.app Text of December 1977 Proposal
.section←null;
.s Goals
Building on a substantial background in computer timesharing system development
(see Appendix C), the Stanford Artificial Intelligence Laboratory
(SAIL) proposes to participate in the Lawrence Livermore Laboratory (LLL)
program for development of the S-1 computer system by designing certain elements
and developing an efficient operating system over a period of three years.
This proposal covers the first 9 months' work.
The proposed work will have the following subgoals:
1) Design and begin development of an operating sysem for both single and
multiprocessor S-1 computer configurations with dedicated disk systems.
This system will provide efficient resource allocation for configurations
of 1 to 32 processors and will include user interactive facilities that
are optimized for display terminals, though teleprinter terminals will
also be supported. In addition to the operating system, a number of
utility programs will be developed, including text editors, file
management programs, compilers, and debuggers.
SAIL recognizes that the S-1 Project requires an evolving operating system
for the various computer configurations it is creating, and will undertake
to create an operating system that will have some minimal capability early
in the effort, growing thereafter in capability in frequent increments.
2) Based on work done in pursuit of the first subgoal, recommend
specific equipment characteristics needed to support efficient
operation. This particularly includes the manner in which
secondary memories and peripherals will connect to various S-1
system configurations.
3) Support S-1 Project hardware development, in fashions and to extents
mutualy agreed upon by cognizant SAIL and LLL staff. During the period of
this initial proposal such support activity will include
detailed design of the crossbar switch for the first S-1 multiprocessor
configuration and the post-construction debugging and documentation of
this hardware module.
.s Work Plan
.ss Operating System Development
The operating system to be developed will exploit the full suite of
capabilities of multiprocessor S-1 configurations and will use the better
features of existing timesharing systems, such as Unix, Multics, TOPS-20,
ITS, and the Stanford Monitor. However, it will also be capable of
specialization for use with single processor S-1 configurations. There
will also be some innovation in interactive user services.
A key problem to be solved is efficient allocation and scheduling of
resources. It should be possible to flexibly allocate processors either
to a number of tasks supporting independent users or to separate forks
of a single task, depending on priorities.
The planning phase of this work (of about three months' duration)
will be devoted to the following tasks:
.bs
(1) familiarization with the S-1 equipment characteristics;
(2) characterization of the principal kinds of computing tasks that are to
be performed with this system;
(3) general design of program services to be provided by the operating
system, including primary memory allocation and file system
characteristics;
(4) general design of user services, including display control, command
languages, and character set standards;
(5) analysis of other resource allocation issues;
(6) study of major existing operating systems to determine which of their
features may be profitably included in the one to be created, and which,
if any, of their major modules may be appropriately carried over into the
new operating system;
(7) formulation of criteria for selection of programming languages to be
used in major development tasks.
.end continue
This phase of the work will culminate with the generation of a
report documenting the results of performing these 7 tasks.
Other products of this phase will include an assortment of planning
documents and specific recommendations on equipment design issues, such
as how the disk storage units should be interfaced to the multiprocessor
system.
The subsequent design phase (of about six months' duration) will focus
on detailed design of the functional elements of the system, selection of
system programming languages, programming of developmental tools (e.g.,
simple editors and debuggers), and possibly the modification of a
compiler to produce S-1 code.
.ss Crossbar Switch Design
It is proposed to design a crossbar switch to connect 16 S-1 processors
with 16 memory modules with a maximum concurrency of 16, and a throughput of
70 nanoseconds per word, as specified in Reference 1.
The switch will contain logic to allow an LSI-11
processor, connected through an LLL-supplied parallel interface, to perform
comprehensive testing of the switch (both by providing artificial stimuli
to the switch, and by reading the state of switch buses and signals) and to
recover from what are considered to be probable recoverable failure modes of
the switch, processors, and memory modules.
SAIL proposes to perform the following subtasks of this basic task
during the current proposal period:
.bs
1) Familiarization of SAIL design personnel with the S-1 Design System.
2) Complete logical design of the switch using the S-1 Design System
Graphics Language.
3) Complete physical design of the switch, including layout and cable
assignment.
4) Production of final wire-lists through the S-1 Design System.
5) Debugging, including demonstration of full switch functionality, using
the LLL-supplied LSI-11 diagnostic system.
6) Documentation, including a structured text description of the hardware
to augment the structured drawings, and a high-level description of switch
operation.
.end
All aspects of crossbar switch hardware implementation is proposed
to be the responsibility of LLL. At the completion of Step 4 (above), it
is proposed that LLL will construct the switch, associated cabinetry, and
LSI-11 debug processor, and will thereupon make the switch available for
debugging by SAIL staff.
Throughout the design, cognizant SAIL staff members will maintain
close contact with cognizant LLL staff members.
.s Facilities
Much of the planning and preliminary programming work on both projects
will be performed on the existing computer facilities of the Stanford
Artificial Intelligence Laboratory. Since this equipment has already been
purchased, mostly with U. S. Government research funds, the only costs
involved in its use will be the support of part of a computer technician
and a share of other maintenance costs.
It is proposed that LLL make available to the Stanford Artificial
Intelligence Laboratory fractions of the capabilities of both single
processor and multiprocessor S-1 configurations appropriate to various
phases of advanced operating systems development and debugging. Determination
of how this is to be most effectively accomplished is to be made
jointly by cognizant LLL and SAIL personnel, as such needs evolve. It is
anticipated that some phone line access to LLL-based S-1 hardware
configurations will be needed and a budget item to support such access is
included.
.s Coordination and Reporting
It is proposed that primary coordination between cognizant LLL and SAIL
staff members be accompished via monthly meetings, to be conducted for
approximately half-day periods. Senior SAIL
Project members will document the salient topics addressed at these
conferences (including accomplishments of the previous month, and the
relatively detailed work plan for the upcoming month) and distribute such
documents to all cognizant SAIL and LLL staff members as the primary project
coordination papers.
SAIL proposes to submit two interim technical reports to LLL dealing
with the progress made during the Winter and Spring Quarters of 1978, and a
final, comprehensive report which treats in detail all aspects of the work
done during the January-September, 1978, period. It is anticipated that the
Winter Quarter document will report the results of the 7-point operating
sysem planning phase discussed in Section 2.1, as well as the first three
items of the crossbar switch development discussed in Section 2.2. It is
likewise expected that the Spring Quarter document will report preliminary
results of the operating system design phase of Section 2.1, and will also
report successful completion of at least 2 of the final 3 items of the switch
development of Section 2.2. The final report will detail the design of the
operating system of Section 2.1, and will include the description of the
switch design implementation and debugging work of Section 2.2. All these
reports will be delivered to LLL within 30 days of the end of the periods on
whose results they report.
.app SAIL Background in System Development
While the primary interests of the Stanford Artificial Intelligence
Laboratory have been in artificial intelligence, mathematical
theory of computation, and related theoretical problems, certain members
of the SAIL staff have been involved for many years in the development of
timesharing systems, programming languages, and interactive facilities.
Some of these activities are outlined below.
The concept of a general purpose timesharing system was first proposed by
John McCarthy when he was at MIT [2]. That proposal led to the pioneering
systems developed in Project MAC. McCarthy also participated in the
development of an early timesharing system at BBN [3].
Shortly after arriving at Stanford in 1962, McCarthy undertook the development
of the first display-oriented timesharing system [4], based on a PDP-1 computer
with 12 displays and a link to an IBM 7090. One notable accomplishment of
this project was the development of a "page editor" called TVEDIT that
exploited the capabilities of displays in text editing. This was the forerunner
of screen editors now in use at SAIL and in a number of other advanced timesharing
systems.
When the SAIL computer facility was assembled in 1966, the staff of the PDP-1
timesharing project became the nucleus of the computer system staff that
developed a display-oriented system on a DEC PDP-6 computer initially and
later on KA10 and KL10 processors.
There are currently 70 display terminals connected to the system, most of
them with full graphics capability [5, 6]. There is also a connection to
the Arpanet, permitting remote access to and from hundreds of other
computers around the world.
In addition to providing conventional timesharing services, this system
handles realtime control of mechanical arms and television cameras, in
support of research in automatic mechanical assembly and computer vision [7].
In the period 1970-73, SAIL staff members designed a high speed processor
known as "Super Foonly", which featured a cache memory, user-accessible
microcode, and a "console computer" (a minicomputer that monitors the main
processor). The latter innovation has since been included in a number of
other machines, including the S-1.
After the design was completed, it was made available to Digital Equipment
Corporation, which used it as the basis for their Decsystem/10 and Decsystem/20
computer systems.
The KL10 processor now at SAIL was donated by DEC out of gratitude for the
design contribution.
Another important outgrowth of this computer design project was a design
automation system known as SUDS [8], which combined interactive drawing
facilities with other computer-aided design services.
This was the first system that permitted a designer, working through a display
terminal, to completely design complex digital devices, including printed
circuit boards and backpanel wiring.
The system automatically produces artwork for PC boards and control tapes for
automatic wiring machines.
SUDS has been used to design five large computers so far, as well as
countless other digital devices.
It is currently in use at MIT, Carnegie-Mellon University, and
Digital Equipment Corporation, among other places, and is the basis of the
S-1 Design System.
Other interests of the SAIL staff include the development of
assemblers [9], the LISP family of programming languages and systems [10, 11, 12],
the SAIL language and compiler [13], text editors [14, 15], interactive
debuggers [16], document compilers [17], and computer communication systems [18].
The backgrounds of the individuals who will carry out the proposed work are
as follows.
John McCarthy, who will provide overall direction of the project,
is a Professor of Computer Science and Director of SAIL.
He has 26 years experience as a faculty
member at a number of major universities and has been a principal innovator
in artificial intelligence, mathematical theory of computation, and timesharing
systems.
Les Earnest, who is Associate Director of SAIL, will handle much of the
management of the project. He has 24 years experience in programming, computer
system design and technical management.
Jeff Rubin, who will head the operating system design effort, is currently
in charge of system programming at SAIL and has twelve years experience as
a programmer, including six years as a system programmer at MIT and four
years in this capacity at SAIL.
Ted Panofsky, who will design the crossbar switch, is head of the SAIL
Computer Facility group, has been a design engineer at SAIL for ten years,
and had several years of electronics experience before that.
Martin Frost has been a systems programmer at SAIL for five years.
.bib;
⊗ Tom McWilliams and Curt Widdoes, "The S-1 Memory Interface",
October 3, 1977.
⊗ John McCarthy, "A Time Sharing Operator Program for our Projected IBM 709",
memo to P. M. Morse, MIT, January 1, 1959.
⊗ John McCarthy, S. Boilen, E. Fredkin, J.C.R. Licklider, "A Time-sharing
Debugging System for a Small Computer", <Proc. AFIP Conf.> (SJCC), Vol. 23,
1963.
⊗ John McCarthy, D. Brian, G. Feldman, J. Allen, "THOR -- A Display Based
Time-sharing System", <Proc. AFIPS Conf.> (FJCC), Vol. 30, Thompson,
Washington, D.C., 1967.
⊗ Brian Harvey and Martin Frost, "Monitor Command Manual", SAILON-54.5,
January 1976.
⊗ McCarthy, John, Lester Earnest, D. Raj. Reddy, Pierre Vicens, "A
Computer with Hands, Eyes, and Ears", <Proc. AFIPS Conf.> (FJCC),
1968.
⊗ Martin Frost, "UUO Manual", SAILON-55.5, October 1977.
⊗ Richard Helliwell, "Stanford Drawing Program", SAIL Program Note, 1971.
⊗ Fred Wright and Ralph Gorin, "FAIL", AIM-226, April 1974.
⊗ John McCarthy, "Recursive Functions of Symbolic Expressions", <Communications
of the ACM>, April 1960.
⊗ John McCarthy, <et al, LISP 1.5 Programmer's Manual,>, MIT Press, 1962.
⊗ David C. Smith, "MLISP User's Manual", AIM-84, January 1969.
⊗ John Reiser (ed.), "SAIL", AIM-289, August 1976.
⊗ William Weiher and Steve Savitzky, "Son of Stopgap", SAILON-50.3, October 1970.
⊗ Arthur Samuel and Martin Frost, "E Text Editor", Program Note, December 1977.
⊗ Phil Petit, "RAID", SAILON-58.1, February 1970.
⊗ Larry Tesler, "PUB, the Document Compiler", SAILON-70, September 1970.
⊗ John McCarthy and Les Earnest, "DIALNET and the Home Terminal", <Proc.
Computer Faire>, San Francisco, 1977.
.end
.next page; app Budget
.skip; once center
Twelve months beginning 1 January 1979
.begin "bud"
.nofill
.turn on "α∂→\{"; tabs 32;
. << put commas in INCR and print it >>
.at "!" incr "∞" ⊂
. if incr≤0 then sal←"" else sal←incr[∞-2 to ∞]; digs←incr/1000;
. while("digs>0",|sal←digs[∞-2 to ∞]&","&sal; digs←digs/1000;|);
. sal;
. ⊃
.macro subtot ⊂
→_______
. ⊃
.macro percent(num) ⊂(((num+50)/100)&"α%")⊃;
.
.tot←0; << total costs >>
.
. << salary = semi*man_months*inflation_factor >>
.at "@" semi "," mo "." frac "∞" ⊂
. annual←(semi*(mo*10+frac)*1023+2500)/5000; tot←tot+annual;
→mo.frac\ →!annual∞
. ⊃
.at "#" amt "∞" ⊂ val←amt; tot←tot+val;
→!val∞
. ⊃
→%3Person\
→Months\
%3A. Salaries and Wages%1
1. Senior Personnel:
a. John McCarthy @1806,0.8∞
Prof. of Computer Science
5α% acad. yr., 10α% summer
b. Forest Baskett @1278,3.5∞
Assoc. Prof. of C.S. & E.E.
25α% acad. yr., 40α% sum.
c. Lester Earnest @1632,1.8∞
Senior Research Associate
15α%
2. Other Personnel (full time except
where specified otherwise):
a. Jeff Rubin @1187,12.0∞
Computer Systems Specialist
b. John Hennessey @972,3.0∞
Asst. Prof. of E.E.
20α% acad. yr., 40α% sum.
c. Arthur Samuel @1500,6.0∞
Adjunct Prof. of C.S.
50α%
d. ---------- @910,12.0∞
Systems Programmer
e. Martin Frost @800,4.0∞
Systems Programmer
f. Mark Lebrun @750,12.0∞
Systems Programmer
g. Armando Rodriguez @666,12.0∞
Systems Programmer
h. Hilding Elmquist @600,3.0∞
Systems Programmer, 25α%
i. Student Res. Assist. @506,7.5∞
50α% acad. yr., 100α% sum.
j. Support Personnel:
(1) Secretary (75α%) @480,9.0∞
(2) Elect. Tech. (25α%) @684,3.0∞
.subtot
Total Salaries & Wages →!tot∞
%3B. Staff Benefits%1 #(tot*2020+5000)/10000∞
19.5α% till 1 Sept.'79,
21.6α% thereafter
%3C. Travel%1 (domestic) #7500∞
%3D. Other direct costs %1 #22700∞
(e.g. telephone, publications,
office supplies, copying,
postage, computer repair services)
%3E. Indirect Costs%1 #(tot*58 +50)/100∞
(58α% of A thru D)
%3F. Permanent Equipment%1 #7200∞
3 Datamedia display terminals
.subtot
.tty←"Total="&tot;
%3G. Total Costs →!tot∞
.end "bud"
.every heading(,,{page});count page; onecol; select 7; verbatim
AN EXTENSION TO THE PROGRAMMING LANGUAGE PASCAL,
TO SUPPORT SYSTEMS PROGRAMMING
John Hennessy
Forest Baskett
November 15, 1978
1.0 INTRODUCTION
This report defines an upward compatible extension of the
programming language Pascal. This extension is designed to support the
construction of large systems programs. A major attempt has been made to
keep the goals of Pascal intact; in particular attention is directed at
simplicity, efficient runtime implementation and efficient compilation,
language security, and compile-time type checking.
1.1 Report
This report consists of four major sections. This first section,
introduces the language and two general extensions. The second section
defines a number of major language features and gives examples. The last
two sections are appendices: the first discusses a number of the major
design decisions behind the features of section2, the second appendix
presents some additional possible extensions which are interesting, but
are either still vague or do not seem necessary.
1.2 Defining Notation
This report uses the BNF notation defined in the Pascal user
Manual. The existing BNF is not repeated but merely referred to (by the
use of nonterminal symbols defined by that grammar).
The semantics are defined informally; a formal axiomatic
definition for the new features may be available later.
1.3 Restrictions
This extension is completely upward compatible with the
Pascal standard, except for one point. This extension requires that
procedures which are parameters be fully typed, by defining the types
of all the parameters and the resultant type in the case of a
function. Thus the grammar for a parameter which is a procedure
becomes:
<formal parameter section> ::= <parameter group>
| var <parameter group>
| <function heading> | <procedure heading>
.next page
1.4 General Extensions
Two minor but general extensions to the language are defined
here. The first is the relaxation of the order of declaration for
constants, types, variables, procedures and functions. These
declaration sections are allowed to occur in any order and may occur any
number of times . It is required that an identifier be declared before
it is used. Pointer types are excluded from this rule. To eliminate
ambiguity, the following rule is introduced:
If a declaration refers to an identifier x, that identifier may
not be declared later in the same scope, if it is declared in a
surrounding scope.
The new syntax for the declaration section becomes:
<block> ::= <label declaration part> <declarations> <statement part>
<declarations> ::= empty | <declaration> <declarations>
<declaration> ::= <constant definition part> | <type definition part>
| <variable declaration part>
| <procedure and function declaration part>
The second extension is to allow the utilization of an
include command. This command with the syntax include <filename>,
will cause the text in the file <filename> to be inserted in line in
the program. The command may appear only where a <block>, or
<declarations> could appear. Thus this construct can be used to
include sets of declarations and/or procedures or functions.
2.0 SPECIFIC EXTENDED LANGUAGE FEATURES
This section defines a number of specific language extensions to
Pascal.
2.1 Type Constructors
<type constructor> ::= <type identifier> (<type specifier> )
<type identifier> ::= identifier
<type specifier> ::= <expression>
|<type specifier> {, <type specifier>}
| ( <type specifier> )
| <type constructor>
Consider a type constructor of the form T ( <type specifier>
). The type name must not be a parameterized type. The form of the
<type specifier> depends on the type name, T. The type T dictates the
form of the type specifier and the result of the type constructor, by
the following rules:
1. Simple type or set type, then the type specifier must be an
expression whose value is implicitly coerceable to the type.
The result is a value of type T equal to the value of the type
specifier expression.
2. Array type, then the type constructor must be a list of values,
whose types match the component type of the array. The result is
a value of the array type T, with the components being the
values in the type specifier. The matching of array components
to values is by increasing indices matched with increasing
positions in the list of values.
.next page
3. Record type, then the type specifier must be a list of values which
match the fields of the record in order of declaration (including
tag field). The result is a value of type T, with the record
fields equal to the corresponding values from the type specifier
list.
Type constructors may appear anywhere a variable of the
constructed type could appear, except that they may not be assigned to.
Furthermore, if all the expressions in a type specifier are compile-time
constants (see next section) then the result is a constant, and may
appear anywhere a constant might appear.
In the type constructor for a string or a packed array of char
the abbreviation 'string of characters', may be used for a list of
character constants; the number of elements in the list must match the
length of the string of characters.
2.1.1 Examples
type T = array [1..3] of integer;
R = record
field: integer;
field2: T;
end;
S = set of 1..20;
const OnetoThree = T (1,2,3);
var x:T;
i,j: integer;
sset: S;
rrecord: R;
type Matrix = array [1..2,1..2] of real;
const DiagMatrix = Matrix ((1,0),(0,1));
begin
i := integer (4*5);
sset := S([1,5..10,17]);
rrecord := R(i,T(i,10,25));
j := i + 45;
x := T (4,5,i*j);
end.
2.2 Extended Constants
<constant definition> ::= <identifier> = <expression>
The concept of a constant is extended to allow a broader class
of defining mechanisms. The first extension is to allow constants to be
defined by any compile-time computable expression. A compile-time
computable expression is defined to be an expression consisting of any
of the following: manifest constants, defined constants, type
constructors, and the standard Pascal operators. The effect of this
extension is two fold: constants may be compile-time expressions, and
constants may be defined of arbitrary types, including structured types.
.next page
2.3 Modules
<module> ::= module <module identifier> <file list>; <block> .
<file list> ::= <empty>
| ( <file identifier> {, <file identifier>} )
The module facility provides the ability to encapsulate
procedures, functions, data and types, as well as supporting separate
compilation. Modules may be separately compiled, and intermodule type
checking will be done as part of the linking process. Unless an
identifier is exported from a module, it is local to that module and
can not be used from other modules. Likewise all identifiers
referenced in a module must be either local or imported from another
module.
2.2.1 Importing and exporting from modules
<declarations> ::= empty | import <declarations> end; <declarations>
| export <declarations> end; <declarations>
| <declaration> <declarations>
<procedure declaration> ::= <procedure heading> external
| <procedure heading> <block>
| <procedure heading> forward
<function declaration> ::= <function heading> external
| <function heading> <block>
| <function heading> forward
Importing allows the use of variables, types, procedures, and
functions which are defined by other modules. Exporting allows a module
to make procedures, functions, variables and types available to other
modules. All exported identifiers are treated as globals to all modules.
In order to reference an object declared by another module, it must be
exported by the declaring module and imported by the accessing module.
Since strong type checking is used, it is highly recommended that types
be exported and imported whenever a variable or procedure requires type
definitions. Import and export sections may not be nested.
2.2.2 An example - defining a stack module
module Stack;
(* defines an integer stack of size <= 100 *)
export
type StackBounds = 0..100;
Stk = record
sp: StackBounds := StackBounds(0);
intstack: array [StackBounds] of integer;
end;
procedure push (var s: stk; item: integer); forward;
function pop (var s: stk): integer; forward;
function empty (s: stk): boolean;
begin
if s.sp = 0 then empty := true else empty := false;
end;
end;
.next page
procedure push (var s:stk; item: integer);
begin
with s do if sp = 100 then ERROR
else begin
sp := succ (sp);
intstack [sp] := item
end
end; (* push *)
function pop (var s: stk): integer;
begin
if empty (s) then ERROR
else with s do begin
pop := intstack[sp];
sp := pred(sp);
end;
end; (* Pop *)
end (* Stack *);
module UseStack;
import
type StackBounds = 1..100;
stk: record
sp: StackBounds := StackBounds(0);
intstack: array [StackBounds] of integer
end;
procedure push (s: stk; i: integer); external;
function pop (s: stk): integer; external;
function empty (s: stk): boolean; external;
end;
var s: stk;
i: integer;
.....
push (s,i);
end (* UseStack *);
(Note that this function is really more suited towards a data
abstraction facility. The module facility is designed to support larger
functional units. The above example is only for illustration.)
.next page
2.4 Variable Initialization
<variable declaration> ::= <identifier> {,<identifier>} : <type> variable init>
<variable init> ::= <empty> | := <type constructor>
<record section> ::= <field identifier> {,<field identifier>} : <type> <variable init>
| <empty>
Variable initialization is only allowed to variables and fields of records at the
global level of a module or a program. The type constructor must be a
constant. All variables in the identifier list or field list are initialized to the
same value.
2.5 Explicit Type Coercion Functions
Explicit type coercion functions which will convert the type
of an expression from one type to another type whose representation
length is the same are provided. These coercion functions take the
form of a predefined set of functions; their implementation is a
compile-time operation of altering the type (no value change is
done).
2.6 Parametric Types
<type definition> ::= <identifier> = <type>
| <parameterized type>
<parameterized type> ::= <identifier> <type parameter list> = <compound type>
<compound type> ::= <array type> | <record type>
<type parameter list> ::= ( <type parameter> {,<type parameter>} )
<type parameter> ::= <identifier> {,<identifier>} : <simple type>
A parameterized type is a type definition where certain
identifiers, which would normally be constants, are allowed to be
unspecified parameters. These parameters can only be used to specify
parameters in a component of the <compound type> or to specify array
bounds. A parameterized array type is an array type with the bounds left
specified as parameters. The identifiers which are type parameters are
local to the type definition. Identifiers within the <array type>
specification which are also in the the type parameter list are bound to
those type parameters. The type parameters can only appear where the
array bounds are being specified (though they may appear in the
specification of the bounds of a component type). Also the bounds must
be specified as subranges, if the parameterized types are used.
Parameterized types allow the implementation of procedures
which may accept a variety of different array sizes. Thus a formal
array parameter can be specified to be a parametric type. All
declarations of variables and constants must supply constant values
for the actual parameters.
Since a parameterized array could be a component of a record,
record types are also allowed to have parameters. However, these
parameters can only be used to define the bounds of arrays within the
record.
Two predefined functions upper and lower are provided. Both
functions take a single parameter of any array type, and return the
lower, or upper bound of that array.
.next page
2.6.1 Example
In this example the stack module is parameterized to allow
variable size stacks.
module Stack;
export
type stackbounds= 1..100;
stk (size: Stackbounds) = record
sp: stackbounds := stackbounds(0);
intstack: array [1..size] of integer;
end;
end;
procedure push (var s: stk; item: integer);
begin
with s do if s.sp=upper(s.intstack) then ERROR
...
...
end; (* STACK *)
var s: stk(20);
i: integer;
...
...
push (s,i);
2.7 Strings
A string facility which provides varying length strings with
a maximum size limit on each string is included. The type string is a
parametric type where the parameter specifies the upper bound on that
string. The logical view on a string is defined by:
type string (n) = record
length : 0..maxint;
text : packed array [1..n] of char;
end
Note that the string package is not really a language extension because
it consists of only a predefined type and a set of predefined procedures
operating on that type.
Pascal string constants of the form 'characters' are treated
as string constants where the actual parameter is the length of the
string. Thus the constant 'ABC', has type string(3), and is
considered an abbreviation for:
type string3 = string(3);
string3(3,'ABC')
.next page
The type string is supported by a variety of predefined
procedures for manipulating strings. These are briefly defined below:
procedure ASSIGN (source: string; var dest:string);
dest <= source
function LENGTH (source: string): 0..maxint;
LENGTH <= source.length
function POS (string1, string2: string): 0..maxint;
POS <= starting position of string1 pattern in string2, else 0
procedure SUBSTR (source: string; var dest: string; sourcepos,
destpos: 1..maxint; leng:0..maxint);
dest.text [destpos..destpos+leng-1] <= source[sourcepos..sourcepos
+leng-1];
dest.leng <= max (dest.length,destpos+length-1);
procedure CONCAT (source: string; var dest: string);
dest.text [dest.length+1..dest.length+1+source.length] <= source.text
dest.length <= dest.length + source.length;
function GETCHAR (source: string; sourcepos:1..maxint): char;
GETCHAR <= source.text[sourcepos];
procedure PUTCHAR (source: char; var dest: string; destpos: 1..maxint);
dest[destpos] := source;
The following string comparasion functions are supplied:
STREQ,STRNE,STRLT,STRGT,STRGE,STRLE.
All take two strings as operands and return true if the relation
holds.
The standard procedures READ and WRITE are adapted to handle
strings.
2.8 Loop-Exit Construct
<loop statement> ::= loop <statement> {; <statement>} end
<exit statement> ::= exit
The loop construct creates an potentially infinite loop, with no
explicit termination condition (unlike the while or for statements).
Within a loop statement one or more exit statements can occur. The
statement exit may only occur within the static nesting of a loop
statement. The semantics of the exit statement are to stop execution of
the immediately surrounding loop statement and begin execution at the
statement following the end of the loop.
.next page
2.9 Packed Structures
Provision is made for specifying two types of storage
packing. If no packing is specified storage is allocated to optimize
access. Packing is only effective on arrays and records.
Specification of the attribute packed will cause a decrease in the
use of storage. The compiler will allocate packed items by
addressable units. Thus each item in a packed array or record will
occupy the next largest addressable unit (byte, halfword, word), that
will accomodate its value range.
The attribute bit packed can only be applied to record types.
It will cause allocation of the fields of a record to be bit packed.
Thus the number of bits occupied by a field will be the minimum
number necessary to hold the range values of that field.
2.10 Storage Management
The implementation will provide a standard procedure DISPOSE,
which takes a single parameter of any pointer type. The result of the
procedure is two-fold: the storage associated with the ptr is freed
(and made eligible for later allocation), and the pointer is set to
NIL.
2.11 Type Coercion
Because the need to occasionally violate the type system is
forseeable, a method for doing this in an explicit manner has been
included. A set of prdefined functions will provide coercion between any
two length compatable types. Note that the coercion functions are
essentially a compile-time vehicle for altering a type. They will not
require any runtime overhead.